package tree.递归;

import po.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N从前序与中序遍历序列构造二叉树105.java
 * @Description TODO https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * @createTime 2021年03月26日 20:10:00
 */
public class N从前序与中序遍历序列构造二叉树105 {
    Map<Integer, Integer> inOrderMap = null;
    private int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLength = preorder.length;
        int inLength = inorder.length;
        this.preorder = preorder;
        inOrderMap = new HashMap<>(inorder.length);
        //todo 根据前序/后序 和 中序遍历的构造，都需要记录中序的每个节点的位置，因为只有中序才可以区分左右子树
        for (int i = 0; i < inorder.length; i++) {
            inOrderMap.put(inorder[i], i);
        }
        //todo 进行递归构造树
        return buildTreeRecurse(0, preLength - 1, 0, inLength - 1);
    }

    /**
     * 前序：
     * [1] [2 4 5 8 9]   [3 6 10 7]
     * pS  ps'     pe'   ps"     pe
     * 中序：
     * [4 2 8 5 9] [1]   [6 10 3 7]
     * is           ri
     * <p>
     * <p>
     * 中序的左子树长度= ri-is
     * 前序的
     * 左子树的  开始  位置: ps'=ps+1
     * 左子树的  结束  位置: pe'=中序的左子树长度+前序的根节点位置 = ri-is+ps
     * 前序的
     * 右子树的  起始  位置= 前序的左子树结束位置+1 = ri-is+ps+1
     * 右子树的  结束  位置=pe
     *
     */
    private TreeNode buildTreeRecurse(int preStart, int preEnd, int inStart, int inEnd) {
        //todo 递归的终止条件
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        //todo 从前序遍历，获取根节点
        int rootValue = preorder[preStart];
        //todo 构造根节点
        TreeNode root = new TreeNode(rootValue);
        //todo 从中序遍历中获取对应根节点的index
        int rootIndex = inOrderMap.get(rootValue);
        //todo 递归构造左子树  这里计算前序遍历的   左子树  的  结束  位置比较复杂
        root.left = buildTreeRecurse(preStart + 1, rootIndex - inStart + preStart, inStart, rootIndex - 1);
        //todo 递归构造右子树，这里计算前序遍历的   右子树  的  起始  位置比较复杂
        root.right = buildTreeRecurse(rootIndex + preStart - inStart + 1, preEnd, rootIndex + 1, inEnd);
        return root;
    }


}
